package leetcode.code1402;

import java.util.Arrays;

public class Solution extends Solution1402 {


	@Override
	public int maxSatisfaction(int[] satisfaction) {
		Arrays.sort(satisfaction);// 做正数菜, 一定合适; 做负数菜, 不一定合适, 分治之前排序
		int len = satisfaction.length;// 数组长度
		if (satisfaction[len - 1] <= 0) {// 全是负数, 不做
			return 0;
		} else if (satisfaction[0] >= 0) {// 全是正数, 全做, 越大的越往后做
			int ans = 0;
			for (int i = 0; i < len; i++) {
				ans += satisfaction[i] * (i + 1);// 满意程度 * 做菜数量
			}
			return ans;
		} else {
			int zero = 0;// 第一个小于0的位置, 不是大于等于0的起始位置
			// 二分找zero
			int l = 0;
			int r = len - 1;
			while (l <= r) {
				int m = ((r - l) >> 1) + l;
				if (satisfaction[m] < 0) {
					zero = m;
					l = m + 1;
				} else {
					r = m - 1;
				}
			}
			int per = 0;// 每增加一道菜, 正数菜整体增加的数量
			int basic0 = 0; // 只做正数菜的基础数量
			int m = 1;// 当前是第m道正数菜
			int n = zero + 1;// 有n道负数菜, 第一个非负菜的位置
			for (int i = n; i < len; i++) {
				per += satisfaction[i];
				basic0 += satisfaction[i] * (m++);
			}
			int basic1 = 0; // 做负数菜产生的正数收益
			int basic2 = 0; // 做负数菜产生的负数收益
			int basic3 = 0; // 做负数菜产生的正负收益
			int[] f = new int[n + 1];// f[i],做第i道负数菜时,负数收益的增量
			for (int j = zero, p = 1; j > -1; j--, p++) {
				f[p] = satisfaction[j] + f[p - 1];
			}
			// 尝试,做i道负数菜
			for (int i = 1; i <= n; i++) {
				basic1 += per;// 做负数菜产生的正数收益增量
				basic2 += f[i];// 做负数菜产生的负数收益增量
				if (basic2 + basic1 >= basic3) {// 收益还在增长就继续尝试
					basic3 = basic2 + basic1;
				} else {
					break;// 收益不增长,上次的basic3就是做负数菜增加的最大收益
				}
			}
			return basic0 + basic3;// 只做正数菜的基础数量 + 做负数菜增加的最大收益
		}
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
